#include<stdio.h>
#include<malloc.h>
#define ERROR 2
#define OK 1
typedef int STATUS;
typedef int ElemType; 

/*
	free(p)
	LNode *p
	p=(LNode*)malloc(sezeof(LNode))
	p -> data = 20
	p -> next = NULL
*/

typedef struct Lnode
{ 
	ElemType data;//数据域,保存数据
	struct Lnode *next;//指针域
}LNode,*LinkList;

/*
	从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，
	然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
	即每次插入的结点都作为链表的第一个结点.
*/

LNode *create_LinkList1(void)//头插法，变得插入顺序逆序
{
	int data;
	
	LNode *head ,*p;
	head = (LNode *)malloc(sizeof(LNode));
	head -> next = NULL;  /* 表头节点 */
	
	while(1)
	{
		scanf("%d",&data);
		if (data == 32767)
			break;

		p = (LNode *)malloc(sizeof(LNode));
		p -> data = data;
		p -> next = head -> next;
		head -> next = p;
	}

	return head;
 }

 LNode *create_LinkList2(void) //尾插法，需要一个控制尾部的指针，但是头部使链表的入口，所以比头插法多一个控制变量
 {
 	int data;
 	LNode *head,*last,*p;//尾插需要三个指针结点，p是不断循环增加的结点，last一直指向最后一个

 	head = (LNode *)malloc(sizeof(LNode));
 	head -> next = NULL;
 	last = head;

 	while (1)//循环条件是死循环，输入错误的数据强制break 32767
 	{
 		scanf("%d",&data);
 		if (data == 32767)
 			break;
 		printf("---------%d\n",data);
 		p = (LNode *)malloc(sizeof(LNode));
 		p -> data = data;
 		p -> next = last ->next;
 		last -> next = p;
 		last = p;
 	}

 	return head;

 }





/*
	单链表按序号查找
	从头结点开始，一直往下扫描，不是随机存取，为顺序存取
*/

ElemType Get_Elem(LNode *L,int i)
{
	int j = 1;
	LNode *p = L -> next;

	while (p != NULL && j < i)  //退出循环条件有两个一个是找到了，一个是输入的位置大于链表长度找到最后一个了
	{
		p = p -> next;
		j++;
	}

	if (j != i)
		printf("填入的序号过大\n");
	else
		return p -> data;
}






/*
	按值查找
	链表和顺序表一样都需要遍历整个表
*/
LNode *Locate_Node(LNode *L,ElemType x)//找到值为x的第一个元素
{//如果要查找第二个x，将通过返回的地址的next再次使用函数往下继续查
	/*
		循环的判断为游标指针p是否为空，跳出循环的条件是p为空即找的值不存在
		第二个条件是找到return  p的地址
	*/
	LNode *p = L -> next;
	
	while (p != NULL)
	{
		if (p -> data == x)
			return p;
		else
			p = p -> next;
	}

	if (p == NULL)
	{
		printf("要查找的元素不存在");
		return NULL;
	}
}







/*
	单链表的插入，头插法和尾插法是建立单链表
	单链表的插入比顺序表方便很多

	需要找到插入结点的前驱
*/
void Insert_LNode(LNode *L,int i,ElemType e)
{//L为头结点的单链表第i个位置插入如值为e的结点
	int j = 0; LNode *p,*q;//需要两个操作指针

	p = L -> next;

	while (p!=NULL && j<i-1)
	{
		p = p -> next;
		j++;
	}

	if (j != i-1)//不已p是否为空判断
		printf("链表长度小于输入的长度或者链表长度为0");
	else
	{
		q = (LNode *)malloc(sizeof(LNode));//不要忘记开辟空间
		q -> data = e;
		q -> next = p -> next;
		p -> next = q;
	}
}







/*
	按序号删除,和查询类似，找到直接前驱
	,插入保证插入序号的前一个结点存在即可，删除需要保证删除的结点存在
*/

void Delete_LNode(LNode *L,int i)
{//删除以L为头结点的单链表的第i个结点
	int j = 1;
	LNode *p,*q;

	p = L;
	q = L -> next;

	while (p -> next != NULL && j<i)
	{
		p = q;
		q = q -> next;
		j++;
	}

	if (j!=i)
		printf("链表长度大于输入的长度或者链表长的为0");
	else
	{	
		p -> next = q -> next;
		free(q);//不要忘记free空间
	}	
}

/*
	按值删除，与按值查找类似，先判断是否存在
*/

void Delete_key_LNode(LNode *L,int key)
{//删除以L为头结点的单链表中值为key的第一个元素
	LNode *p = L;
	LNode *q = L -> next;

	while (q != NULL && q-> data == key)
	{
		p = q;
		q = q -> next;
	}

	if (q -> data == key)
	{
		p -> next = q -> next;
		free(q);
	}
	else
	{
		printf("索要删除的结点不存在\n");
	}
}

void Delete_allkey_LNode(LNode *L,int key)
{//删除所有key值
	LNode *p = L;
	LNode *q = L -> next;

	while (q!=NULL)
	{
		if (q -> data == key)
		{
			p -> next = q -> next; 
			free(q);
			q = p -> next;//继续赋值循环
		}
		else
		{
			p = q;
			q = q -> next;
		}
	}
}

void Delete_allsame_LNode(LNode *L)
{//删除所有重复的值 时间复杂度为n平方
 /*
	降低时间复杂度的方法，牺牲空间复杂度
 */
	LNode *p = L -> next;
	LNode *q,*r;

	while (p != NULL)
	{
		q = p;
		r = p -> next;
		while (r != NULL)
		{
			if (r ->data == p ->data)
			{
				q -> next = r -> next;
				free(r);
				r = q -> next;
			}
			else
			{
				q = r;
				r = r -> next;
			}
		}

		if (r == NULL)
			p = p -> next;
	}
}

/*
	单链表的合并.两个有序的单链表，
	它们的头指针分别是La,Lb,将它们合并为Lc为头指针的有序链表
*/

LNode *Merge_LinkList(LNode *La,LNode *Lb)
{
	/*
		最好的时间复杂度是O(min(m.n))
		最差的情况运行了m+n-1次，时间复杂度为O(m+n)
		也可写为O(max(m,n))
		因为当两个值越来越大多项式去大头的原则主要是受到最大的影响 
	*/
	LNode *Lc,*pa,*pb,*pc,*ptr;
	Lc = La;
	pc = La;
	pa = La -> next;
	pb = Lb -> next;

	while (pa != NULL && pb != NULL)
	{
		if (pa -> data < pb -> data)
		{
			pc -> next = pa;
			pc = pa;
			pa = pa -> next;
		}

		if (pa -> data > pb -> data)
		{
			pc -> next = pb;
			pc = pb;
			pb = pb -> next;
		}

		if (pa -> data == pb -> data)
		{/*两个值相等删除pb，
		   如果保留pb则将第一个if判断改成小于等于即可
		*/
			pc ->next = pa;
			pc = pa;
			ptr = pb;
			pb = pb -> next;
			free(ptr);
		}
	}

	if (pa != NULL)
		pc -> next = pa;
	else
		pc -> next = pb;

	free(pb);

	return Lc;
}

int main(void)
{

}